package org.basis.algorithm.sort.practice;

import org.basis.algorithm.common.SortUtil;

import java.util.ArrayList;
import java.util.List;

/**
 * 排序练习2
 *
 * @author Mr_wenpan@163.com 2021/12/09 11:46
 */
public class SortPractice02 {
    public static void main(String[] args) {
        int[] array = SortUtil.generateRandomArray(20, 30);
//        bubbleSort(array);
//        insertionSort(array);
//        selectionSort(array);
//        mergeSort(array);
        quickSort(array);
        int[] arr = new int[]{0, 1, 2, 3, 4, 5};
//        heapSort(arr);
        SortUtil.printArr(arr);
        SortUtil.printArr(array);

        List<List<Integer>> lists = subList(arr);
        System.out.println(lists);
    }

    private static void bubbleSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    SortUtil.swap(j, j + 1, arr);
                }
            }
        }
    }

    private static void insertionSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        for (int i = 1; i < arr.length; i++) {
            for (int j = i; j > 0; j--) {
                if (arr[j] < arr[j - 1]) {
                    SortUtil.swap(j, j - 1, arr);
                }
            }
        }
    }

    private static void selectionSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            int minPosition = i;
            for (int j = i; j < arr.length; j++) {
                if (arr[minPosition] > arr[j]) {
                    minPosition = j;
                }
            }
            SortUtil.swap(i, minPosition, arr);
        }
    }

    private static void mergeSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        doMergeSort(arr, 0, arr.length - 1);
    }

    private static void doMergeSort(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = left + (right - left) / 2;
        doMergeSort(arr, left, mid);
        doMergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }

    private static void merge(int[] arr, int left, int mid, int right) {
        int[] help = new int[right - left + 1];
        int p = left;
        int q = mid + 1;
        int index = 0;

        while (p <= mid && q <= right) {
            if (arr[p] <= arr[q]) {
                help[index] = arr[p];
                index++;
                p++;
            } else {
                help[index] = arr[q];
                index++;
                q++;
            }
        }

        // 有任意一边到达边界
        while (p <= mid) {
            help[index] = arr[p];
            p++;
            index++;
        }

        while (q <= right) {
            help[index] = arr[q];
            index++;
            q++;
        }

        // 拷贝回原数组
        for (int i = 0; i < help.length; i++) {
            arr[left + i] = help[i];
        }
    }

    private static void quickSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        doQuickSort(arr, 0, arr.length - 1);
    }

    private static void doQuickSort(int[] arr, int left, int right) {
        // basecase
        if (left >= right) {
            return;
        }
        int[] partition = partition(arr, left, right);
        doQuickSort(arr, left, partition[0]);
        doQuickSort(arr, partition[1], right);
    }

    private static int[] partition(int[] arr, int left, int right) {
        int p = left - 1;
        int q = right;
        int index = left;
        while (index < q) {
            if (arr[index] < arr[right]) {
                SortUtil.swap(index++, ++p, arr);
            } else if (arr[index] > arr[right]) {
                SortUtil.swap(index, --q, arr);
            } else {
                index++;
            }
        }

        // 交换最后一个元素
        SortUtil.swap(right, index, arr);

        return new int[]{p, q};
    }

    private static void heapSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        // 先将数组构建为大根堆
        for (int i = 0; i < arr.length; i++) {
            // 父节点
            int p = (i - 1) / 2;
            int j = i;
            // 当前节点大于父节点，则交换
            while (arr[j] > arr[p]) {
                SortUtil.swap(i, p, arr);
                j = p;
                p = (j - 1) / 2;
            }
        }

        // 把大根堆的堆顶元素换到堆底
        for (int i = arr.length - 2; i >= 0; i--) {
            SortUtil.swap(0, i, arr);
            heapify(arr, 0, i);
        }
    }

    private static void heapInsert(int[] arr, int index) {
        // 找到父节点
        int p = (index - 1) / 2;
        while (arr[index] > arr[p]) {
            SortUtil.swap(index, p, arr);
            index = p;
            p = (index - 1) / 2;
        }
    }

    private static void heapify(int[] arr, int index, int heapSize) {
        int lc = 2 * index + 1;
        while (lc < heapSize) {
            // 左右孩子值最大的下标
            int largest = lc + 1 >= heapSize ? arr[lc] : (arr[lc] > arr[lc + 1]) ? lc : lc + 1;
            // 最大的孩子都比他小
            if (arr[largest] <= arr[index]) {
                break;
            }
            SortUtil.swap(largest, index, arr);
            index = largest;
            lc = 2 * index + 1;
        }
    }

    /**
     * 求arr的子数组
     */
    private static List<List<Integer>> subList(int[] arr) {
        List<List<Integer>> resList = new ArrayList<>();
        // 对于每个位置都求一个包含他本身在内的所有子数组
        for (int i = 0; i < arr.length; i++) {
            // 从i位置向后取子数组
            for (int j = i; j < arr.length; j++) {
                List<Integer> list = new ArrayList<>();
                // 求从i ~ j位置上的数据组成的子数组
                for (int k = i; k <= j; k++) {
                    list.add(arr[k]);
                }
                // 将子数组加入结果集
                resList.add(list);
            }
        }

        return resList;
    }
}
